package PriorityQueue;

public class MinTopPile<E extends Priority> implements Queue<E> {

    private Priority[] arr;
    private int size;

    public MinTopPile(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() > value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
        arr[i] = value;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //先交换
        swap(0,size - 1);
        size--;
        E ret = (E)arr[size];
        arr[size] = null;
        //下潜
        down(0);
        return ret;
    }
    private void swap(int i, int j) {
        E t = (E)arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    private void down(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int min = i;
        if (left < size && arr[min].priority() > arr[left].priority() ) {
            min = left;
        }
        if (right < size && arr[min].priority() > arr[right].priority()) {
            min = right;
        }
        if (min != i) {
            swap(i,min);
            down(min);
        }
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }

        return (E)arr[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}
